// Pipit 集合数据结构模块
#include "pipit_stdlib.h"
#include <stdlib.h>
#include <string.h>

// 动态数组
typedef struct pipit_vector {
    void** items;
    size_t count;
    size_t capacity;
    size_t item_size;
} pipit_vector_t;

// 哈希表
typedef struct pipit_hashmap {
    char** keys;
    void** values;
    size_t* hashes;
    size_t count;
    size_t capacity;
} pipit_hashmap_t;

// 链表节点
typedef struct pipit_list_node {
    void* data;
    struct pipit_list_node* next;
} pipit_list_node_t;

// 链表
typedef struct pipit_list {
    pipit_list_node_t* head;
    pipit_list_node_t* tail;
    size_t count;
} pipit_list_t;

// 栈
typedef struct pipit_stack {
    void** items;
    size_t top;
    size_t capacity;
} pipit_stack_t;

// 队列
typedef struct pipit_queue {
    void** items;
    size_t front;
    size_t rear;
    size_t count;
    size_t capacity;
} pipit_queue_t;

// 动态数组实现
pipit_vector_t* pipit_vector_create(size_t item_size) {
    pipit_vector_t* vec = malloc(sizeof(pipit_vector_t));
    vec->items = NULL;
    vec->count = 0;
    vec->capacity = 0;
    vec->item_size = item_size;
    return vec;
}

void pipit_vector_push_back(pipit_vector_t* vec, void* item) {
    if (vec->count >= vec->capacity) {
        vec->capacity = vec->capacity == 0 ? 4 : vec->capacity * 2;
        vec->items = realloc(vec->items, vec->capacity * sizeof(void*));
    }
    vec->items[vec->count++] = item;
}

void* pipit_vector_get(pipit_vector_t* vec, size_t index) {
    if (index >= vec->count) return NULL;
    return vec->items[index];
}

size_t pipit_vector_size(pipit_vector_t* vec) {
    return vec->count;
}

void pipit_vector_destroy(pipit_vector_t* vec) {
    if (vec) {
        free(vec->items);
        free(vec);
    }
}

// 哈希表实现
pipit_hashmap_t* pipit_hashmap_create() {
    pipit_hashmap_t* map = malloc(sizeof(pipit_hashmap_t));
    map->capacity = 16;
    map->count = 0;
    map->keys = calloc(map->capacity, sizeof(char*));
    map->values = calloc(map->capacity, sizeof(void*));
    map->hashes = calloc(map->capacity, sizeof(size_t));
    return map;
}

static size_t pipit_hash(const char* str) {
    size_t hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

void pipit_hashmap_set(pipit_hashmap_t* map, const char* key, void* value) {
    size_t hash = pipit_hash(key);
    size_t index = hash % map->capacity;
    
    // 检查是否已存在
    for (size_t i = 0; i < map->capacity; i++) {
        size_t probe_index = (index + i) % map->capacity;
        if (map->keys[probe_index] == NULL) {
            map->keys[probe_index] = strdup(key);
            map->values[probe_index] = value;
            map->hashes[probe_index] = hash;
            map->count++;
            break;
        } else if (map->hashes[probe_index] == hash && strcmp(map->keys[probe_index], key) == 0) {
            map->values[probe_index] = value;
            break;
        }
    }
    
    // 扩容
    if (map->count >= map->capacity * 0.7) {
        size_t old_capacity = map->capacity;
        map->capacity *= 2;
        char** old_keys = map->keys;
        void** old_values = map->values;
        size_t* old_hashes = map->hashes;
        
        map->keys = calloc(map->capacity, sizeof(char*));
        map->values = calloc(map->capacity, sizeof(void*));
        map->hashes = calloc(map->capacity, sizeof(size_t));
        map->count = 0;
        
        for (size_t i = 0; i < old_capacity; i++) {
            if (old_keys[i]) {
                pipit_hashmap_set(map, old_keys[i], old_values[i]);
                free(old_keys[i]);
            }
        }
        
        free(old_keys);
        free(old_values);
        free(old_hashes);
    }
}

void* pipit_hashmap_get(pipit_hashmap_t* map, const char* key) {
    size_t hash = pipit_hash(key);
    size_t index = hash % map->capacity;
    
    for (size_t i = 0; i < map->capacity; i++) {
        size_t probe_index = (index + i) % map->capacity;
        if (map->keys[probe_index] == NULL) break;
        if (map->hashes[probe_index] == hash && strcmp(map->keys[probe_index], key) == 0) {
            return map->values[probe_index];
        }
    }
    return NULL;
}

// 链表实现
pipit_list_t* pipit_list_create() {
    pipit_list_t* list = malloc(sizeof(pipit_list_t));
    list->head = NULL;
    list->tail = NULL;
    list->count = 0;
    return list;
}

void pipit_list_push_back(pipit_list_t* list, void* data) {
    pipit_list_node_t* node = malloc(sizeof(pipit_list_node_t));
    node->data = data;
    node->next = NULL;
    
    if (list->tail) {
        list->tail->next = node;
    } else {
        list->head = node;
    }
    list->tail = node;
    list->count++;
}

void* pipit_list_get(pipit_list_t* list, size_t index) {
    if (index >= list->count) return NULL;
    
    pipit_list_node_t* current = list->head;
    for (size_t i = 0; i < index && current; i++) {
        current = current->next;
    }
    return current ? current->data : NULL;
}

// 栈实现
pipit_stack_t* pipit_stack_create(size_t capacity) {
    pipit_stack_t* stack = malloc(sizeof(pipit_stack_t));
    stack->items = malloc(capacity * sizeof(void*));
    stack->top = 0;
    stack->capacity = capacity;
    return stack;
}

int pipit_stack_push(pipit_stack_t* stack, void* item) {
    if (stack->top >= stack->capacity) return -1;
    stack->items[stack->top++] = item;
    return 0;
}

void* pipit_stack_pop(pipit_stack_t* stack) {
    if (stack->top == 0) return NULL;
    return stack->items[--stack->top];
}

// 队列实现
pipit_queue_t* pipit_queue_create(size_t capacity) {
    pipit_queue_t* queue = malloc(sizeof(pipit_queue_t));
    queue->items = malloc(capacity * sizeof(void*));
    queue->front = 0;
    queue->rear = 0;
    queue->count = 0;
    queue->capacity = capacity;
    return queue;
}

int pipit_queue_enqueue(pipit_queue_t* queue, void* item) {
    if (queue->count >= queue->capacity) return -1;
    queue->items[queue->rear] = item;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->count++;
    return 0;
}

void* pipit_queue_dequeue(pipit_queue_t* queue) {
    if (queue->count == 0) return NULL;
    void* item = queue->items[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->count--;
    return item;
}